// m

// 给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列

// 解题思路，跟全排列1的不同之处在于增加了序列中的元素可重复这一条件
// 这就涉及到了去重，先对nums进行排序，然后使用visited数组标记该元素在当前排列中是否被访问过
// 如果未被访问过则将其加入排列中，并在访问后将该元素变为未访问状态



function permuteUnique(nums) {
    let res = []
    let path = []
    function backtrack(nums, visited) {
        if (path.length === nums.length) {
            res.push([...path])
            return
        }
        for (let i = 0; i < nums.length; i++) {
            // 上一个相同的元素相同 且刚被撤销访问
            if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) {
                continue
            }
            if (!visited[i]) {
                visited[i] = true
                path.push(nums[i])
                backtrack(nums, visited)
                path.pop()
                visited[i] = false
            }
        }
    }
    nums.sort((x, y) => x - y)
    let visited = new Array(nums.length).fill(false)
    backtrack(nums, visited)
    return res
}

let nums = [1, 1, 2, 1]
console.log(permuteUnique(nums))